\documentclass{llncs}[11pt]

\def\isanonymous{0}
\def\isshort{0}

\usepackage{ifthen}
\newcommand{\anonymous}[2]{
\ifthenelse{\equal{\isanonymous}{1}}
{{#1}}
{{#2}}
}

\newcommand{\submission}[2]{\ifthenelse{\equal{\isshort}{1}}{{#1}\xspace}{{#2}\xspace}}


\ifthenelse{\equal{\isshort}{0}}{
\usepackage{a4wide}
}{}

\usepackage[utf8x]{inputenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{xspace}
\usepackage{tikz,pgfplots}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Speed up compilation by caching Tikz picktures
%
% when you change a tikz picture run: 
%
%  pdflatex -shell-escape bkw-small-secret
%
% You can also simply comment out the two lines below to go back 
% to the normal behaviour
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usetikzlibrary{external}
%\tikzexternalize[prefix=figures/] % activate!

\usepackage{embedfile}

\usepackage{url}
\usepackage[vlined,linesnumbered]{algorithm2e}

\usepackage[index,multiuser]{fixme}
\fxsetup{
    status=draft,
    layout=pdfcnote,
    theme=color
}

\FXRegisterAuthor{malb}{amalb}{malb}
\FXRegisterAuthor{lp}{alp}{lp}
\FXRegisterAuthor{rf}{arf}{rf}

\newcommand\LWE{\ensuremath{{\rm LWE}}\xspace}
\newtheorem{assumption}{Assumption}

\newcommand{\tildeO}[1]{\ensuremath{\tilde{\mathcal{O}}(#1)}\xspace}

\newcommand{\heading}[1]{{\vspace{6pt}\noindent\sc{#1.}}}

\newcommand{\bigO}[1]{\ensuremath{\mathcal{O}\left(#1\right)}\xspace}
\newcommand{\poly}{ {\rm poly}(n)}
\newcommand{\chig}{\ensuremath{\chi_{\alpha,q}}}
\newcommand{\chis}{\ensuremath{\psi}}
\newcommand{\U}[1]{\ensuremath{\mathcal{U}(#1)\xspace}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}\xspace}
\newcommand{\Zq}{\ensuremath{\mathbb{Z}_q}\xspace}
\newcommand{\Zp}{\ensuremath{\mathbb{Z}_p}\xspace}
\newcommand{\Zqchi}{\ensuremath{\mathbb{Z}^{\Phi_{\zeta}}_q}[\vec{x}]\xspace}
\newcommand{\Ldis}{L_{\mathbf{s},\chi}\xspace}

\newcommand{\Bdis}[1]{B_{\mathbf{s},\chi}(b,#1,p)\xspace}
\newcommand{\Bdissm}[1]{B_{small,\mathbf{s},\chi}(b,#1,p)\xspace}
\newcommand{\sample}{\ensuremath{\leftarrow_{\$}}}

\newcommand{\CDF}[1]{\textnormal{CDF}\left(#1\right)\xspace}
\newcommand{\E}{\ensuremath{\textnormal{E}}}
\newcommand{\Var}{\ensuremath{\textnormal{Var}}}

\newcommand{\abs}[1]{\ensuremath{\left|#1\right|}\xspace}

\renewcommand{\vec}[1]{\mathbf{#1}\xspace}
\newcommand{\shortvec}[1]{\tilde{\mathbf{#1}}\xspace}
\newcommand{\mat}[1]{\ensuremath{\mathbf{#1}}\xspace}

\newcommand{\dotp}[2]{\ensuremath{\left\langle {#1},{#2}\right\rangle}\xspace}
\newcommand{\N}[1]{\ensuremath{\mathcal{N}({#1)}}}
\newcommand{\round}[1]{\ensuremath{\left\lfloor{#1}\right\rceil}\xspace}

\def\abn{\lceil n/b \rceil}


\title{Lazy Modulus Switching for the BKW Algorithm on LWE}
\anonymous{\author{} \institute{}}{
\author{Martin R.~Albrecht \inst{1} \and Jean-Charles Faugère \inst{3,2,4} \and Robert Fitzpatrick \inst{5} \and Ludovic Perret \inst{2,3,4}}
\institute{
Technical University of Denmark, Denmark \and
Sorbonne Universités, UPMC Univ Paris 06, POLSYS, UMR 7606, LIP6, F-75005, Paris, France \and
INRIA, Paris-Rocquencourt Center, POLSYS Project\and
CNRS, UMR 7606, LIP6, F-75005, Paris, France \and
Information Security Group\\
Royal Holloway, University of London\\
Egham, Surrey TW20 0EX, United Kingdom \\ 
\email{maroa@dtu.dk, jean-charles.faugere@inria.fr, robert.fitzpatrick.2010@live.rhul.ac.uk, ludovic.perret@lip6.fr}  
}}


\parindent 0em
\parskip 0.9em

\begin{document}

\maketitle

\begin{abstract}
Some recent constructions based on LWE do not sample the secret uniformly at random but rather from some distribution which produces small entries. The most prominent of these is the binary-LWE problem where the secret vector is sampled from $\{0,1\}^{\ast}$ or $\{-1,0,1\}^{\ast}$. We present a variant of the BKW algorithm for binary-LWE and other small secret variants and show that this variant reduces the complexity for solving binary-LWE. We also give estimates for the cost of solving binary-LWE instances in this setting and demonstrate the advantage of this BKW variant over  standard BKW and lattice reduction techniques applied to the SIS problem. Our variant can be seen as a combination of the BKW algorithm with a lazy variant of modulus switching which might be of independent interest.
\end{abstract}

\input{intro_new.tex}

\input{algorithm.tex}

\submission{}{\input{implementation.tex}}

\input{parameters.tex}

\section{Conclusion \& Future Work}

We investigated applying modulus switching to exploit the presence of a small secret in LWE instances and demonstrated that it can make a significant impact on the complexity of solving such instances. We also adapted the BKW algorithm to perform modulus-switching `on-the-fly', showing that this approach is superior to performing `one-shot' modulus reduction on LWE samples prior to solving. Our first variant improves the target modulus by a factor of $\sqrt{\log_2 n}$ in typical scenarios; our second variant mainly improves the memory requirements of the algorithm, one of the key limiting aspects of the BKW algorithm. Our algorithms, however, rely on various assumptions which, though appearing sound, are unproven. Our estimates should thus be considered heuristic, as are performance estimates for all currently-known algorithms for solving LWE. Verifying these assumptions is hence a promising direction for future research. Furthermore, one of the main remaining obstacles for applying the BKW algorithm to cryptographic constructions based on LWE is that it requires an unbounded number of samples to proceed. Lifting this requirement, if only heuristically, is hence a pressing research question.

\section*{Acknowledgement}
We thank Steven Galbraith for helpful comments on an earlier draft of this work. We also thank anonymous referees for detailed comments which greatly improved this work. Jean-Charles Faugère, and Ludovic Perret  have been partially supported supported by the Computer Algebra and Cryptography (CAC) project (ANR-09-JCJCJ-0064-01) and the HPAC grant (ANR ANR-11-BS02-013) of the French National Research Agency. 

\bibliographystyle{plain}
\bibliography{bkw-small-secret}

\end{document}
